The present invention relates generally to content addressable memories (CAMs) and more particularly to test modes and test methods for CAMs.
Due to the increasing importance of data networks, including the Internet, applications for content addressable memories (CAMs) have continued to proliferate. CAMs, also sometimes referred to as xe2x80x9cassociative memories,xe2x80x9d can provide rapid matching functions that are often needed in certain packet processing hardware devices, such as routers and network switches, to name just two. In a typical packet processing operation, a device can receive a data packet. The packet can include a xe2x80x9cheaderxe2x80x9d that includes various data fields that indicate how the packet should be processed. The device can use a matching function, provided by a CAM, to compare one or more header fields to xe2x80x9clook-upxe2x80x9d tables stored in the CAMs.
A typical CAM can store the data values of a look-up table in one or more CAM cell arrays. CAM cell arrays can be configured into a number of entries, each of which can provide a match indication. In a compare (i.e., match) operation, data values stored within CAM entries can be compared to a comparand value (also referred to as a xe2x80x9csearch keyxe2x80x9d). In a typical packet processing device, the comparand value can include a field extracted from a data packet header. If a data value matches an applied comparand value, the corresponding entry can generate an active match indication. If a data value does not match an applied comparand value, the corresponding entry can generate an inactive match indication (signifying a xe2x80x9cmismatchxe2x80x9d) condition.
For many CAM applications it can be desirable to have entries arranged with a predetermined priority. In the event two or more match indications are activated in response to an applied comparand value, one of the match indications can be selected according to the priority of its corresponding entry.
Referring now to FIG. 6, a representation of a CAM having entries with multiple matches is depicted in table form. A CAM according to FIG. 6 may include eight entries, labeled 0 to 7. Also shown in FIG. 6 is a 68-bit comparand value 600. In this example, lower numbered entries can have priority over higher numbered entries. Thus, if the application of a comparand value resulted in entries 1, 4 and 5 activating a match indication, the match indication of entry 1 can have priority over that of entries 4 and 5.
To better understand the structure of the CAM and the use of a priority encoder, a conventional approach is shown in FIG. 7 and is designated by the general reference character 700. Referring to FIG. 7, a CAM 700 may include CAM cells identified as 702-yx, where y indicates a particular row and x indicates a particular column. CAM cells of a same row can belong to the same entry 704-0 to 704-y. CAM cells of an entry 704 can store data for comparison with a comparand value. Each entry (704-0 to 704-y) may provide a match indication MATCH0-MATCHy after comparing a comparand to entry values.
Match indications MATCH0-MATCH-y can be generated on match lines 706-0 to 706-y, respectively. Match lines (MATCH0-MATCH-y) may then be amplified with a match line""s respective match sense amplifier (MSA), designated by 708-0 to 708-y. Match sense amplifiers 708-0 to 708-y can produce output signals MATCH0xe2x80x2 to MATCHyxe2x80x2. Resulting signals MATCH0xe2x80x2 to MATCHyxe2x80x2 can be buffered in registers 716-0 to 716-y. Subsequently, the registers 716-0 to 716-y may output signals PE0 to PEy that are used as inputs to a match/priority encoder (M/P.E.), designated by 714.
It is noted that a CAM 700 may also generate a match flag. A match flag may be activated when at least one entry generates a match indication. A match flag may be generated by a conventional circuit that logically combines all match outputs to determine the presence of at least one active match indication (e.g., a logical ORing of match indications). Such a match flag is shown in FIG. 7 MATCH_FLAG as an output from a M/P.E. 714 in FIG. 7. However, it is understood that a match circuit that generates a match flag (MATCH_FLAG) may be entirely separate from a priority encoder circuit.
A M/P.E. 714 may output values ROM0 to ROMy, which may generally be encoded values corresponding to a matching entry 704 with the highest priority. Such M/P.E. 714 output values (ROM0 to ROMy) may be applied to a read-only-memory (ROM) 718 to generate an index value INDEX.
A M/P.E. 714 may further include a multiple match detection circuit. Multiple match detection circuits may detect when more than one match indication is generated. In the particular example of FIG. 7, a multiple match detection circuit within a M/P.E. 714 may generate a multiple match signal (MULT) that is active when more than one match indication is generated.
For further details on the operation of particular priority encoders, one may reference U.S. Pat. No. 6,268,807 xe2x80x9cPriority encoder/read only memory (ROM) combinationxe2x80x9d issued to Miller et al. on Feb. 1, 2000.
The conventional ROM approach of FIG. 7 generates an index value. Such a value may be conceptualized as xe2x80x9cassociatedxe2x80x9d data. That is, an associated data value may be generated corresponding to each CAM entry. However, associated data may take a variety of other forms. As but two of the many possible examples, associated data may be stored in memory cells connected directly or indirectly to a match line and/or indication. In addition, an index value itself may be applied to another circuit and/or device to generate additional associated data (e.g., a index may form all or a portion of a RAM device address).
Of course, a CAM may only generate match indications, and does not necessarily have to generate or otherwise point to associated data.
Testing memories devices, such as CAMs, can be an important step in a manufacturing process. Testing may detect process defects, enable device repair, and provide an indication of device reliability. Testing may occur on a device level and/or a xe2x80x9cboardxe2x80x9d level (i.e., after a device has been packaged and installed). In the case of detecting process defects, devices may be tested in wafer-form and/or in a finished package.
A test on a semiconductor device may cycle through all of the entries to insure functionality of all the CAM cells. Once the defective CAM cells are identified, a device may be repaired with redundant memory. The test time and equipment needed to achieve a given material throughput can have a direct impact on the cost of manufacturing the device. Thus, reductions in test time and/or necessary test equipment can reduce manufacturing costs.
For a CAM with a priority encoder, a testing time can be compounded by the fact that a priority encoder typically outputs an encoded address of a first match location. As noted above, simultaneous matches lower in priority may go undetected. Therefore, when testing an entry, all entries higher in priority may be forced to a mismatch so that an entry of interest can be singled out as matching or mismatchingxe2x80x94and hence tested.
Referring once again to FIG. 6, a first conventional testing of a priority encoded CAM will now be described. When targeting entry 4 for testing, all entries with higher priority (entries 0 to 3) may be forced to a mismatch with the comparand data. In this way, entry 4 may be examined to see if the entry is a match or mismatch. In this case, entry 1 may conventionally be rewritten with mismatching data before entry 4 is tested. Such a conventional approach of ensuring higher order mismatches can add to testing algorithm complexity and/or increased test time when testing a CAM with a priority encoder.
Another conventional testing method may provide a more efficient approach to testing CAM entries. Such a second conventional method may include writing different data values to each entry. Such different data values may then be applied to as comparand values to the CAM. In a xe2x80x9cgoodxe2x80x9d part, one match indication should be generated for each unique comparand value. This more efficient approach can still require multiple cycles and xe2x80x9cnxe2x80x9d comparand values will have to be applied for xe2x80x9cnxe2x80x9d entries. Further, provided each entry stores binary data, for entries of x bits, if there are more than 2x entries on a CAM, unique values for each entry are not possible. Consequently, in such cases only portions of a CAM may be tested at one time using this approach.
In light of the above, it would be desirable to arrive at some way of testing a CAM that identifies mismatches or errors. Additionally, it would be desirable to have some means of verifying matches without having to sequence through highest to lowest priorities. It would also be advantageous to have a method to reduce test time and have reduced algorithm complexity when compared to conventional approaches.
According to disclosed embodiments, a content addressable memory (CAM) may includes a number of entries that can store data values. In response to an applied comparand value, each entry can generate a match indication. Match indications can be received by a switch circuit. Each entry can further generate a mismatch indication in response to an applied comparand value. Mismatch indications can also be received by a switch circuit. A switch circuit may selectively output match indications or mismatch indications.
According to one aspect of the embodiments, match indications and mismatch indications from the CAM cells can be applied to the same priority encoder.
According to another aspect of the embodiments, in response to match indications, a priority encoder can generate a highest priority match indication. In response to mismatch indications, a priority encoder can generate a highest priority mismatch indication.
According to another aspect, a switch circuit can include multiplexer circuits.
According to another aspect of the embodiments a switch circuit may output match indications in a first mode, mismatch indications in a second mode, and predetermined logic states in a third mode.
According to another aspect of the embodiments, a CAM may include a match detection circuit that can receive match indications or mismatch indications. A match detection circuit can provide a flag. A flag can indicate that at least one match indication is active in one mode, or at least one mismatch indication is active in another mode.